public class test07 {
    class Solution {
        public int lastStoneWeightII(int[] stones) {
            //问题转换为：两堆重量最相近的石头情况
            //类比分割等和子集问题
            int sum = 0;
            for(int stone:stones){
                sum += stone;
            }
            int target = sum/2;
            int[][] dp = new int[stones.length][target+1];
            //初始化
            for(int j = stones[0];j<=target;j++){
                dp[0][j] = stones[0];
            }

            for(int i = 1;i<stones.length;i++){
                for(int j = 0;j<=target;j++){
                    if(j>=stones[i]){
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                    }else{
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            return sum - dp[stones.length-1][target]*2;
        }
    }
}
